#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    /**
     * @brief 超出时间限制
     *
     * @param staple
     * @param drinks
     * @param x
     * @return int
     */
    int breakfastNumber(vector<int> &staple, vector<int> &drinks, int x)
    {
        sort(staple.begin(), staple.end(), greater<int>());
        sort(drinks.begin(), drinks.end(), greater<int>());
        int ans = 0;
        int stapleLen = staple.size(), drinksLen = drinks.size();
        for (size_t i = 0; i < stapleLen; i++)
        {
            // for (size_t j = 0; j < drinksLen; j++)
            // {
            //     if (staple[i] + drinks[j] <= x)
            //     {
            //         ans++;
            //     }
            // }
            int j = 0;
            while (j < drinksLen)
            {
                if (staple[i] <= x - drinks[j])
                {
                    ans += drinksLen - j;
                    break;
                }
                j++;
            }
        }
        return ans % int(1e9 + 7);
    }

    int breakfastNumber(vector<int> &staple, vector<int> &drinks, int x)
    {
        sort(staple.begin(), staple.end());
        sort(drinks.begin(), drinks.end());

        int i = 0;
        int j = drinks.size() - 1;
        long ans = 0;

        while (i < staple.size() && j >= 0)
        {
            int sum = staple[i] + drinks[j];
            if (sum <= x)
            {
                i++;
                ans += j + 1;
                ans %= 1000000007;
            }
            else
            {
                j--;
            }
        }

        return ans % 1000000007;
    }

    int breakfastNumber_4(vector<int> &staple, vector<int> &drinks, int x)
    {
        int drinks_record[100001] = {0};
        for (auto one : drinks)
        {
            drinks_record[one]++;
        }
        for (int i = 1; (i < 100001) && (i < x); i++)
        {
            drinks_record[i] += drinks_record[i - 1];
        }
        long result = 0;
        for (auto one : staple)
        {
            result += drinks_record[x > one ? ((x - one) >= 100001 ? 100000 : x - one) : 0];
        }
        return result % 1000000007;
    }
};
int main()
{
    Solution s;
    vector<int> staple = {2, 1, 1}, drinks = {8, 9, 5, 1};
    int x = 9;
    cout << s.breakfastNumber(staple, drinks, x) << endl;
    return 0;
}